package biolabs.model.division

import biolabs.space.ContinuousPosition
import biolabs.space.DiscretePosition
import biolabs.space.GridShapedObject

import java.util.{Deque, LinkedList, List => JList}

/**
 * A space divider that executes flood fill simultaneously from two points
 * of the occupied space. The area flooded from the first point stays in
 * the current bio-object, the area flooded from the second point is the
 * space for the daughter bio-object.
 *
 * @author Tomas Mikula
 */
trait FloodFillSpaceDivider[
	P <: DiscretePosition[P, C],
	C <: ContinuousPosition[C, P]
] extends SpaceDivider[P] {
self: DivisionEndsDeterminator[P] with GridShapedObject[P, C] =>

	/**
	 * Divides the space of this bio-object between
	 * this (old) bio-object and the new bio-boject.
	 *
	 * Assigns each element currently occupied by this bio-object
	 * to either this bio-object or the new bio-object:
	 * <ol>
	 *  <li> {@code oldEnd} is assigned to the old bio-object,
	 *    {@code newEnd} to the new bio-object;
	 *  <li> while there are unassigned elements:
	 *   <ul>
	 *     <li>if there are unassigned elements reachable from {@code oldEnd}
	 *       through elements already assigned to the old bio-object, the one
	 *       closest to {@code oldEnd} is assigned to the old bio-object;
	 *     <li>if there are unassigned elements reachable from {@code newEnd}
	 *       through elements already assigned to the new bio-object, the one
	 *       closest to {@code newEnd} is assigned to the new bio-object.
	 *   </ul>
	 * </ol>
	 *
	 * @return the list of grid elements to be occupied by the new bio-object.
	 */
	override def calculateDaughterSpace(): JList[P] = {
		val (oldEnd, newEnd) = determineDivisionEnds()
		val oldSpace = new LinkedList[P]();
		val newSpace = new LinkedList[P]();
		val oldSpaceCandidates = new LinkedList[P]();
		val newSpaceCandidates = new LinkedList[P]();
		oldSpaceCandidates.add(oldEnd);
		newSpaceCandidates.add(newEnd);

		// elements to be divided
		val space = new java.util.HashSet[P](getShape().getElements());

		class Capturer {
			def capture(candidates: Deque[P], target: JList[P]): Boolean = {
				while(!candidates.isEmpty()){
					val p = candidates.removeFirst();
					if(space.remove(p)){
						target.add(p);
						candidates.addAll(p.getNeighbors());
						return true;
					}
				}
				return false;
			}
		}
		val capturer = new Capturer();
		while(capturer.capture(oldSpaceCandidates, oldSpace) && capturer.capture(newSpaceCandidates, newSpace)) {}
		while(capturer.capture(newSpaceCandidates, newSpace)){}
		assert(newSpace.size() < getShape().getVolume());
		return newSpace;
	}
}